1. Introduction: The Nature of Computing Science Research

Computer Science is an unusual discipline. It is partly mathematics, partly natural science and partly engineering. Because of this, it accepts more than one kind of evidence, and a researcher must know which kind of evidence his or her particular question demands.

1.1 The Three Paradigms of Computing

1. Theory (the mathematics paradigm). Rooted in mathematics. The researcher defines objects, states theorems, and proves them. Steps: definition → theorem → proof → interpretation. Example: proving that a problem is NP-complete.
2. Abstraction (the scientific paradigm). Rooted in experimental science. The researcher forms a hypothesis, constructs a model, designs an experiment, collects data and analyses it. Example: hypothesising and then measuring how cache size affects execution time.
3. Design (the engineering paradigm). Rooted in engineering. The researcher states requirements and specifications, designs and implements a system, and then tests it. Example: designing a new distributed file system and evaluating it.

1.2 Why a Method is Necessary

A result in computing science is accepted not because the researcher is confident, but because the method used to obtain it can withstand examination. The method is the guarantee; the result is only the outcome.

2. The Dialectic of Research in Computing Science

2.1 Meaning of Dialectic

The word comes from the Greek dialektike, meaning the art of debate. In research it means that knowledge is not created by one person announcing a fact; it is created by a community testing that fact until it survives.

2.2 The Classical Dialectical Triad

1. Thesis: the initial claim or position. “Algorithm A is faster than Algorithm B.”
2. Antithesis: the opposition, objection or contradictory evidence. “Algorithm A is faster only for small inputs; for large inputs its memory use causes thrashing.”
3. Synthesis: the refined position that accounts for both. “Algorithm A outperforms B for inputs below the cache size; beyond that, B is superior.”

The synthesis then becomes a new thesis, and the cycle repeats. This is why research is described as cyclical rather than linear.

2.3 How the Dialectic Operates in Computing Science

1. Peer review. A paper is sent to reviewers whose professional duty is to doubt it. Their objections are the antithesis; the revised paper is the synthesis.
2. Conference discussion and rebuttal. Presentation is followed by questions that attack assumptions, baselines and generality.
3. Replication and refutation. Later researchers repeat the experiment. If the result does not reproduce, the claim is weakened or withdrawn.
4. Competing methods and benchmarks. Shared datasets and benchmark suites (SPEC, TPC, ImageNet, CIC-IDS) exist precisely so that rival claims can be compared on neutral ground.
5. Counterexamples. In theory, one valid counterexample destroys a universal claim permanently.
6. The “Related Work” and “Threats to Validity” sections of a paper are dialectic written down: the author states rival positions and the weaknesses of his or her own work.

2.4 Importance of the Dialectical Method

1. It removes personal bias, because a claim must survive people who want it to fail.
2. It exposes hidden assumptions that the author could not see.
3. It improves the precision of claims — vague claims cannot survive attack.
4. It builds cumulative, reliable knowledge instead of isolated opinions.
5. It protects the discipline against error, exaggeration and fraud.
6. It generates new research problems, since every unresolved objection is a fresh gap.

3. Models of Argument

3.1 What is an Argument in Research?

An argument is not a quarrel. It is the logical skeleton of every research paper.

3.2 The Toulmin Model of Argument

The most widely used model of argument has six components. This is a standard 10-mark question — learn all six with one running example.

1. Claim. The conclusion you want the reader to accept.
   “Our caching scheme reduces average page-load time.”
2. Evidence (Data / Grounds). The facts, measurements or proofs that support the claim.
   “Across 500 page loads, the mean load time fell from 820 ms to 610 ms.”
3. Warrant. The reasoning that connects the evidence to the claim — the bridge that explains why this evidence supports this claim. This is the component students most often omit.
   “A statistically significant reduction in measured mean load time under an identical workload indicates an improvement caused by the caching scheme.”
4. Backing. Support for the warrant itself — established theory, accepted practice or prior literature that makes the warrant credible.
   “Controlled benchmarking with repeated trials is the accepted evaluation method in systems research.”
5. Qualifier. The words that limit the strength or scope of the claim: usually, in most cases, for workloads of this type, with 95% confidence. A qualifier makes a claim honest and defensible.
   “For read-heavy workloads, load time is reduced by 20–28%.”
6. Rebuttal. The stated conditions under which the claim would not hold, and the researcher's response to anticipated objections.
   “For write-heavy workloads the invalidation cost dominates and no improvement is observed.”

3.3 Types of Argument Used in Computing Science

1. Deductive argument. From general principles to a specific, necessary conclusion. If the premises are true, the conclusion must be true. Example: every comparison-based sort requires Ω(n log n) comparisons; MergeSort is comparison-based; therefore MergeSort cannot beat Ω(n log n).
2. Inductive argument. From specific observations to a general, probable conclusion. Example: the system crashed under high load on 28 separate occasions; therefore it probably crashes under high load in general.
3. Abductive argument (inference to the best explanation). From an observation to the most plausible cause. Example: response time spikes exactly when the garbage collector runs; therefore GC pauses are the most likely cause. Abduction generates hypotheses; it does not prove them.
4. Argument by analogy. A conclusion drawn because two situations are similar in relevant respects. Example: a technique that improved TCP congestion control may improve congestion control in a data-centre protocol. Analogy suggests; it never proves.
5. Argument by authority or citation. Relying on established, peer-reviewed results. Legitimate when the source is reliable and relevant; a fallacy when it replaces evidence.
6. Argument by counterexample. Disproving a universal claim by exhibiting a single case that violates it. Extremely powerful in theoretical computing.

3.4 Structure of the Argument in a Research Paper

3.5 Logical Fallacies to Avoid

This matters because a reviewer's objection is almost never “your numbers are wrong”; it is far more often “your numbers do not support what you are claiming from them”. Fallacies are usually grouped into two families:

1. Formal fallacies: the structure of a deductive argument is itself invalid, regardless of the subject matter. Example: “if the cache were the bottleneck, throughput would fall under load; throughput fell under load; therefore the cache is the bottleneck” — this affirms the consequent and silently ignores every other possible cause of the slowdown.
2. Informal fallacies: the structure looks fine, but a premise is irrelevant, unsupported, or smuggled in from insufficient data, rhetoric or authority rather than evidence. Almost all of the fallacies below are informal, and they are the ones that recur most often in empirical computing-science papers and B.Tech./M.Tech. project reports.

1. Hasty generalization: concluding from too few observations (one run, one dataset). Example: calling a new caching policy “superior” after testing it on a single benchmark trace.
2. Post hoc ergo propter hoc: assuming that because B followed A, A caused B. Example: latency dropped after a runtime upgrade, so the upgrade is credited, while a simultaneous hardware change is ignored.
3. Cherry-picking: reporting only the favourable results. Example: publishing the best of ten experimental runs and omitting the other nine.
4. Straw man: comparing against a deliberately weak or badly configured baseline. Example: benchmarking a proposed algorithm only against an unoptimised brute-force implementation.
5. Circular reasoning: assuming in the premises what the conclusion is meant to prove. Example: “the protocol is secure because it follows secure design principles, and it follows secure design principles because it is secure”.
6. Appeal to authority: “it must be right, a famous group published it”. Example: adopting a design choice uncritically because a well-known lab used it, without checking whether it fits the current problem.
7. False dichotomy: presenting only two options when more exist. Example: “either accept O(n²) blow-up or use my algorithm”, ignoring hybrid or approximate approaches.
8. Correlation–causation confusion: treating an association as a cause. Example: memory usage and crash rate both rise across software versions, so memory growth is blamed, when a third factor (a shared dependency update) could explain both.

4. Proof Methods in Computing Science

Computing science accepts three principal kinds of proof. Choosing the wrong one is a frequent cause of rejection.

4.1 Demonstration (Proof by Construction)

Characteristics

1. It answers the question “Is this possible?”
2. It is an existence proof: building one working instance proves feasibility.
3. It is the natural method of the design/engineering paradigm.
4. It is the dominant method in B.Tech. and M.Tech. projects.

Steps

1. State the requirement or specification precisely.
2. Design the artifact.
3. Implement it.
4. Show that it satisfies the specification under stated conditions.
5. Report the environment, assumptions and limitations.

Strengths and limitations

• Strengths: concrete, convincing, immediately useful, produces a usable artifact.
• Limitations: proves only that it worked there, then, under those conditions; it does not prove generality, optimality or correctness in all cases.

4.2 Empirical Proof

Characteristics

1. It answers the question “Does this hold generally, in practice?”
2. It is the method of the abstraction/scientific paradigm.
3. It is inductive: the conclusion is probable, never certain.
4. Its conclusions are valid only inside the range of conditions that were tested.

Requirements of a sound empirical proof

1. A clearly stated hypothesis, framed before the experiment.
2. A fair baseline — the best available existing method, properly configured.
3. Well-defined metrics chosen in advance.
4. A representative and clearly described workload and environment.
5. Control of variables — only one factor changes at a time.
6. Repetition — multiple runs, with mean and variation reported.
7. Statistical testing — p-values, confidence intervals, effect sizes.
8. Reproducibility — enough detail (versions, parameters, seeds, data) that others can repeat it.

Strengths and limitations

• Strengths: tells you what really happens in the messy real world, including effects that theory omits.
• Limitations: never certain; costly and time-consuming; results may not transfer to other hardware, data or workloads.

4.3 Mathematical Proof

Characteristics

1. It answers the question “Is this guaranteed to be always true?”
2. It is the method of the theory/mathematics paradigm.
3. It is deductive: if the assumptions hold, the conclusion cannot be false.
4. It requires no testing — no number of experiments can add to or subtract from it.

Principal techniques of mathematical proof

1. Direct proof. Assume the hypothesis and derive the conclusion by a chain of valid steps. Example: the sum of two even numbers is even.
2. Proof by contraposition. To prove P ⇒ Q, prove ¬Q ⇒ ¬P. The two statements are logically equivalent. Example: to prove “if n² is even, then n is even”, prove the contrapositive instead — “if n is odd, then n² is odd”.
3. Proof by contradiction (reductio ad absurdum). Assume the claim is false and derive an impossibility. Example: prove that there is no largest natural number — assume N is the largest; then N+1 is a larger natural number, a contradiction.
4. Proof by mathematical induction. Prove the base case, assume the statement holds for k (the induction hypothesis), and prove it for k+1.
   P(1) ∧ (∀k  P(k) ⇒ P(k+1))  ⇒  ∀n  P(n)
   Example: prove 1+2+…+n = n(n+1)/2 for every n ≥ 1.
5. Proof by cases. Break the problem into a finite set of possibilities and prove the claim in each one separately. Example: prove that the square of any integer is either even or odd — consider the case where the integer is even and the case where it is odd.
6. Constructive proof. Prove that something exists by explicitly constructing it. Example: prove that an even prime number exists — the number 2 is even and has exactly two factors, 1 and 2, so it is prime.

4.4 Comparison of the Three Proof Methods

5. Deduction and Induction for Computer Science

5.1 Deductive Reasoning

Form

The classical form is the syllogism:

• Major premise: All comparison-based sorting algorithms require Ω(n log n) comparisons in the worst case.
• Minor premise: QuickSort is a comparison-based sorting algorithm.
• Conclusion: QuickSort requires Ω(n log n) comparisons in the worst case.

Validity vs. soundness

• An argument is valid if the conclusion follows logically from the premises.
• It is sound if it is valid and the premises are actually true.
• A valid argument with false premises gives a false conclusion — this is why assumptions must be stated explicitly.

Where deduction is used in computing

1. Complexity analysis and asymptotic bounds.
2. Proving algorithm correctness (invariants, induction).
3. Formal verification and model checking.
4. Type systems and compiler correctness.
5. Database theory — normalization, query equivalence.
6. Cryptographic security proofs.
7. Logic programming (Prolog) and automated theorem proving.

5.2 Inductive Reasoning

Form

• Observation: On 28 evenings the network throughput fell after 21:00 hrs.
• Conclusion: The network throughput generally falls after 21:00 hrs.

The 29th evening may contradict this. That permanent uncertainty is called the problem of induction.

Where induction is used in computing

1. All benchmarking, performance measurement and profiling.
2. Software testing — passing tests suggests, but never proves, correctness.
3. Machine learning — generalizing from training data to unseen data is inductive by nature.
4. Empirical software engineering, user studies and surveys.
5. Data mining and pattern discovery.
6. Repository mining and defect prediction.

5.3 Abductive Reasoning

Abduction infers the most plausible explanation for an observation. It is how debugging works: the program crashes only on large inputs, therefore a buffer overflow is the most likely explanation. Abduction generates hypotheses; deduction predicts their consequences; induction tests them.

5.4 Comparison of Deduction and Induction

5.5 The Hypothetico-Deductive Cycle

Real research uses both directions in a loop:

You observe a phenomenon, guess an explanation, deduce what must follow if the guess is right, test that prediction empirically, and revise. Deduction gives certainty about consequences; induction gives contact with reality. Research needs both.

6. Theoretical Models and Approaches

6.1 Abstraction: The Central Idea

Abstraction is deliberate, careful forgetting. The researcher removes every detail that does not affect the question, leaving a clean structure that can be reasoned about exactly.

6.2 Steps in the Theoretical Approach

1. Identify the essential entities and relationships in the problem.
2. Choose or construct a suitable formal model.
3. State assumptions and definitions precisely.
4. Formulate the claim as a theorem or lemma.
5. Prove it using an appropriate proof technique.
6. Interpret the result back in terms of the original real-world problem.
7. State the limits of the abstraction.

6.3 Important Formal Models in Computing Science

1. Automata and formal languages: finite automata, pushdown automata, Turing machines — models of computation and of what can be computed.
2. Computability theory: decidability, the Halting Problem, reducibility.
3. Complexity theory: classes P, NP, NP-complete, NP-hard, PSPACE; lower and upper bounds.
4. Graph models: networks, dependencies, scheduling, routing, social structures.
5. Mathematical logic: propositional and predicate logic, temporal logic (used to specify properties of concurrent systems).
6. Lambda calculus and type theory: foundations of functional programming and type systems.
7. Process algebras (CCS, CSP, π-calculus): models of concurrent and communicating systems.
8. Petri nets: modelling concurrency, synchronization and deadlock.
9. Queueing theory and Markov chains: models of performance and stochastic behaviour.
10. Information theory: entropy, channel capacity, compression limits.
11. Game theory: modelling strategic interaction in networks, auctions and security.

6.4 Formal Methods and Verification

• Formal specification: writing the required behaviour in a precise mathematical notation (Z, VDM, Alloy, TLA+).
• Theorem proving: deriving correctness with tools such as Coq, Isabelle or PVS.
• Model checking: automatically and exhaustively exploring all reachable states of a finite model to check whether a property holds; produces a counterexample trace when it fails. Tools: SPIN, NuSMV, UPPAAL.
• State-space explosion is the main practical limitation of model checking.

6.5 Strengths and Limitations

• Strengths: results are certain, general and permanent; they apply to systems that do not exist yet; they can prove impossibility, which no experiment can do.
• Limitations: the abstraction may omit factors that dominate in practice (cache behaviour, constant factors, hardware effects); asymptotically superior algorithms are sometimes slower on real input sizes; strong mathematical background is required.

7. Algorithmic Approaches

An algorithm is not a research contribution until three things are established: it is correct, it terminates, and its cost is bounded.

7.1 Algorithm Design Paradigms

1. Brute force / exhaustive search: try all possibilities. Simple, correct, usually too slow.
2. Divide and conquer: split, solve recursively, combine. Example: MergeSort, FFT.
3. Greedy: take the locally best choice at each step; requires proof that this yields the global optimum. Example: Dijkstra, Huffman coding.
4. Dynamic programming: solve overlapping sub-problems once and store the results. Example: Floyd–Warshall, sequence alignment.
5. Backtracking and branch-and-bound: systematic search with pruning. Example: N-Queens, integer programming.
6. Randomized algorithms: use random choices; analysis is in terms of expected behaviour. Example: randomized QuickSort, Miller–Rabin primality test.
7. Approximation algorithms: accept a provably bounded distance from optimal in exchange for polynomial running time. Example: 2-approximation for vertex cover.
8. Heuristic and metaheuristic methods: genetic algorithms, simulated annealing, particle swarm. No optimality guarantee; evaluated empirically.
9. Online algorithms: decisions must be made without knowledge of future input; evaluated by competitive ratio.
10. Parallel and distributed algorithms: evaluated additionally by speedup, scalability and communication cost.

7.2 Proving Algorithm Correctness

1. Loop invariants for iterative algorithms (initialization, maintenance, termination).
2. Mathematical induction for recursive algorithms.
3. Exchange argument for greedy algorithms — show that any optimal solution can be transformed into the greedy one without becoming worse.
4. Optimal substructure and overlapping sub-problems for dynamic programming.
5. Termination argument: identify a quantity that strictly decreases and is bounded below.

7.3 Complexity Analysis

Asymptotic notations

• O(g(n)) — asymptotic upper bound (at most).
• Ω(g(n)) — asymptotic lower bound (at least).
• Θ(g(n)) — tight bound (both).
• o(g(n)) and ω(g(n)) — strict upper and lower bounds.

Cases and kinds of analysis

• Worst case — the guarantee; most commonly reported.
• Best case — rarely useful on its own.
• Average case — requires an assumed input distribution, which must be stated.
• Amortized analysis — average cost per operation over a worst-case sequence of operations (e.g. dynamic array doubling).
• Space complexity — memory consumed, increasingly the binding constraint in practice.
• Communication and I/O complexity — dominant in distributed and big-data settings.

Recurrence relations

The running time of a recursive algorithm is expressed as a recurrence, e.g. for MergeSort:

Recurrences are solved by substitution, recursion trees, or the Master Theorem.

7.4 Empirical Algorithmics

Asymptotic analysis hides constant factors and hardware effects. Therefore theoretical analysis is normally accompanied by experimental algorithmics: implementing the algorithm, running it on realistic inputs, and measuring actual time, memory and cache behaviour. Theory tells you how the cost grows; measurement tells you what the cost is.

8. Software Engineering Approaches

Here the object of study is not only the program but also the process and the people. This makes the evidence noisier and the methods closer to social science.

8.1 Research Methods in Software Engineering

1. Constructive / design-science research: build a new method, tool or framework and evaluate it. The most common approach in SE research and in student projects.
2. Controlled experiment: subjects (often students or developers) perform tasks under controlled conditions; e.g. comparing debugging time with and without a new tool.
3. Case study: in-depth investigation of one real project or organisation in its natural context; e.g. studying a migration from a monolith to microservices.
4. Survey research: questionnaires or interviews with a sample of practitioners to learn practices, opinions and difficulties.
5. Systematic Literature Review (SLR) and mapping study: a rigorous, protocol-driven review of all published evidence on a question, with explicit inclusion and exclusion criteria.
6. Mining Software Repositories (MSR): analysing version-control history, issue trackers and code reviews to discover patterns; e.g. predicting defect-prone modules from commit history.
7. Action research: the researcher participates in solving a real organisational problem and studies the intervention.
8. Ethnographic / observational study: observing developers at work to understand actual practice rather than reported practice.
9. Benchmarking and tool evaluation: comparing tools on common subject programs.
10. Simulation of processes: modelling the software process to predict effort or defect flow.

8.2 Measurement in Software Engineering

• Product metrics: lines of code, cyclomatic complexity, coupling and cohesion, code smells, test coverage, defect density.
• Process metrics: effort, cycle time, defect removal efficiency, churn, review latency.
• Resource/people metrics: team size, experience, productivity (to be used with great caution).
• Quality models: ISO/IEC 25010 attributes — functionality, reliability, usability, efficiency, maintainability, portability, security.

8.3 Threats to Validity in Empirical SE

1. Internal validity: is the observed effect really caused by the treatment, or by some uncontrolled factor?
2. External validity: do results obtained with student subjects or toy programs generalize to industry?
3. Construct validity: does the metric truly capture the concept (does lines-of-code really measure productivity)?
4. Conclusion validity: is the statistical analysis appropriate and the sample large enough?

9. Mathematical Modelling

9.1 Why Model?

1. To predict behaviour before a system is built — when measurement is impossible.
2. To study conditions that are too costly, too large or too dangerous to create.
3. To understand why a system behaves as it does, not merely that it does.
4. To explore many design alternatives cheaply.
5. To optimize parameters analytically.
6. To provide a theoretical explanation for measured data.

9.2 Steps in Mathematical Modelling

1. Identify the problem and the questions the model must answer.
2. State assumptions and simplifications explicitly.
3. Identify variables and parameters: input, output, state, decision variables.
4. Formulate relationships as equations, inequalities or probability distributions.
5. Solve the model analytically or numerically.
6. Verify — is the model implemented correctly? (Are we building the model right?)
7. Validate — does the model agree with reality? (Are we building the right model?)
8. Perform sensitivity analysis — how do the results change when parameters vary?
9. Interpret and apply the results; state the range of validity.

9.3 Classification of Models

9.4 Common Mathematical Models in Computing

1. Queueing models: servers, arrival rates and service rates — the standard model of CPUs, networks, disks and cloud services.
2. Markov chains: systems that move between states with given probabilities — reliability, caching, PageRank.
3. Graph models: routing, dependency, scheduling and social networks.
4. Optimization models: linear programming, integer programming, convex optimization — used in resource allocation and scheduling.
5. Probabilistic and statistical models: distributions of arrival times, failures and errors.
6. Reliability models: MTBF, MTTR, availability = MTBF/(MTBF+MTTR).
7. Cost and effort models: COCOMO for software effort estimation.
8. Machine-learning models viewed as function approximators fitted to data.

9.5 A Worked Model: The M/M/1 Queue

Consider a single server (a CPU, a web server or a network link) with Poisson arrivals at rate λ and exponential service at rate μ.

9.6 Little's Law

One of the most useful and general results in performance modelling:

where L is the average number of items in a system, λ the average arrival rate, and W the average time each item spends in the system. It holds for almost any stable system, regardless of the arrival or service distribution.

9.7 Verification vs. Validation of a Model

9.8 Advantages and Limitations

• Advantages: inexpensive, fast, safe, allows what-if analysis, gives insight into cause and effect, applicable to systems not yet built.
• Limitations: results are only as good as the assumptions; real workloads are often not Poisson; over-simplification produces confident but wrong predictions; over-complication makes the model unsolvable.

10. Performance Estimation and Evaluation

10.1 Objectives of Performance Evaluation

1. To compare two or more alternative designs, algorithms or systems.
2. To identify bottlenecks in an existing system.
3. To determine whether a system meets its performance requirements.
4. To predict performance under future or larger loads (capacity planning).
5. To tune parameters for optimal operation.
6. To justify the claim made in a research paper.

10.2 Performance Metrics

1. Response time / latency: time from request to response. Report the median and the 95th or 99th percentile, not only the mean.
2. Throughput: work completed per unit time (requests/second, transactions/second, FLOPS).
3. Utilization: fraction of time a resource is busy.
4. Execution time: total time to complete a task.
5. Speedup: S = T_old/T_new, or T₁/T_n for parallel systems.
6. Efficiency: E = S/n for n processors.
7. Scalability: how performance changes as load or resources grow.
8. Reliability and availability: MTBF, MTTR, uptime percentage.
9. Energy and power: joules per operation — increasingly important.
10. Cost: price per unit of performance.
11. Accuracy-related metrics (for ML systems): accuracy, precision, recall, F1-score, AUC.

10.3 Techniques of Performance Evaluation

10.4 Workload Characterization

• The workload is the set of requests or inputs applied to the system during evaluation.
• Real workload: actual traces from production. Most realistic, least repeatable.
• Synthetic workload: generated to resemble real behaviour. Repeatable and controllable.
• Standard benchmarks: SPEC CPU (processors), TPC-C/TPC-H (databases), LINPACK (supercomputers), YCSB (key-value stores), MLPerf (machine learning), ImageNet and CIC-IDS (datasets). Benchmarks make results comparable across research groups.
• A workload must be representative of actual use; a benchmark that exercises only the favourable path proves nothing.

10.5 Designing a Performance Experiment

1. State the goal and the specific question.
2. Choose the metrics before running anything.
3. Identify the factors (variables you will change) and their levels.
4. Identify and control the parameters you will hold constant.
5. Select the workload and the baseline for comparison.
6. Decide the number of repetitions; use different random seeds where applicable.
7. Discard warm-up periods (cache and JIT effects) before recording.
8. Run the experiment, recording the full environment.
9. Analyse using appropriate statistics; report mean/median with variation.
10. Present results clearly and state the limitations.

10.6 Fundamental Laws of Performance

Amdahl's Law

If a fraction p of a program can be parallelized and the remaining (1−p) is inherently sequential, then with n processors the speedup is

Interpretation: the sequential portion sets a hard ceiling on speedup. If 10% of a program is sequential, no number of processors can give more than a 10× speedup.

Gustafson's Law

For problems whose size grows with the available computing power, the scaled speedup is

Interpretation: in practice we use bigger machines to solve bigger problems, so the outlook is less pessimistic than Amdahl's Law suggests.

Little's Law

L = λW — as stated in Section 9.6.

The bottleneck principle

Overall system performance is limited by its slowest component. Optimizing a non-bottleneck component yields no improvement — a direct consequence of Amdahl's Law.

10.7 Common Mistakes in Performance Evaluation

This list is frequently asked and is also the most practically useful part of the unit.

1. No stated goal — measuring whatever is easy to measure.
2. Unfair or weak baseline — comparing an optimized new system against an unoptimized or badly configured old one (the straw-man fallacy).
3. Wrong or single metric — reporting throughput while ignoring latency, or reporting only the mean while hiding a terrible tail.
4. Unrepresentative workload — testing with tiny inputs, or only on the best-case data.
5. Single run — one measurement is an anecdote; variation is unknown.
6. Ignoring warm-up effects — including cold caches, JIT compilation or page faults in the measurement.
7. Uncontrolled environment — background processes, thermal throttling, network traffic and other users affecting results.
8. Measurement overhead (probe effect) — the profiler itself changing the behaviour measured.
9. Omitting variability — reporting a single number with no standard deviation or confidence interval.
10. Improper statistics — averaging ratios incorrectly (use the geometric mean for speedup ratios, the harmonic mean for rates).
11. Confusing statistical with practical significance — a 0.4% improvement that is statistically real but operationally useless.
12. Over-generalizing — claiming results hold on all hardware and workloads when only one was tested.
13. Selective reporting — omitting the experiments where the method performed poorly.
14. Irreproducible reporting — not stating versions, parameters, seeds or data sources.

10.8 Presenting Performance Results

• Use graphs with clearly labelled axes and units; state the number of repetitions.
• Show error bars, box plots or confidence intervals — never a bare bar chart of single runs.
• Use log scales when values span orders of magnitude.
• Report percentiles for latency; means hide the tail that users actually notice.
• Provide a table of the exact experimental configuration for reproducibility.

11. Putting It Together: A Worked Example

A research group claims: “Our new channel-assignment algorithm improves evening throughput in dense Wi-Fi deployments.” Unit II tells us what is required before this claim can be accepted.

12. Chapter Summary

1. Computing science has three paradigms — theory, abstraction and design — and therefore three corresponding proof methods.
2. Dialectic means truth is reached through claim, opposition and refined synthesis; peer review, replication and benchmarking are its practical forms.
3. An argument (Toulmin model) has six parts: claim, evidence, warrant, backing, qualifier and rebuttal. The warrant — the bridge from evidence to claim — is the part students omit.
4. Types of argument: deductive, inductive, abductive, by analogy, by authority, by counterexample.
5. Demonstration proves possibility, empirical proof proves practical generality, mathematical proof proves certainty. Good research combines them.
6. Mathematical proof techniques include direct, contraposition, contradiction, induction, cases and construction.
7. Deduction moves from general to specific and is certain; induction moves from specific to general and is probable. Mathematical induction is deductive despite its name.
8. The theoretical approach abstracts a problem into a formal model (automata, graphs, logic, complexity classes) and proves results that hold universally.
9. The algorithmic approach requires three things: correctness, termination and a complexity bound.
10. The software engineering approach studies systems, processes and people using experiments, case studies, surveys, SLRs and repository mining, and must always report threats to validity.
11. Mathematical modelling represents a system by equations; models must be both verified (built right) and validated (right model). Key results: M/M/1 queueing and Little's Law.
12. Performance evaluation requires a goal, correct metrics, a representative workload, a fair baseline, repetitions and honest statistics. Amdahl's Law bounds achievable speedup.

13. Glossary of Key Terms

14. Examination Practice Questions

14.1 Very Short Answer (2 marks each)

1. Define dialectic in the context of research.
2. State the three paradigms of computing science.
3. What is a warrant in the Toulmin model of argument?
4. Differentiate between validity and soundness of an argument.
5. Distinguish between mathematical induction and inductive reasoning.
6. What is a proof by counterexample? Give an example.
7. Define partial correctness and total correctness.
8. What is a loop invariant?
9. State Amdahl's Law and explain what it implies.
10. State Little's Law and give one application.
11. What is meant by the probe effect?
12. Differentiate between verification and validation of a model.
13. Define speedup and efficiency in parallel computing.
14. What is a baseline in performance evaluation, and why must it be fair?
15. What is meant by state-space explosion?

14.2 Short Answer (5 marks each)

1. Explain the dialectical nature of research in computing science with suitable examples.
2. Explain the six components of the Toulmin model of argument using one running example.
3. Compare demonstration, empirical proof and mathematical proof.
4. Explain any five techniques of mathematical proof used in computer science.
5. Differentiate between deductive and inductive reasoning with computing examples.
6. Explain the hypothetico-deductive cycle of research.
7. What is abstraction? Explain its role in theoretical computer science with an example.
8. Explain the steps involved in mathematical modelling.
9. Explain the M/M/1 queueing model and what it tells us about heavily utilized servers.
10. Describe any five research methods used in empirical software engineering.
11. Explain the four types of threats to validity in an empirical study.
12. What is workload characterization? Why is a representative workload essential?
13. List and explain any six common mistakes in performance evaluation.
14. Explain the logical fallacies that a researcher must avoid.

14.3 Long Answer (10 marks each)

1. Explain the dialectic of research in computing science. Discuss models of argument and explain how a research paper is structured as an argument.
2. Explain in detail the three proof methods used in computing science — demonstration, empirical and mathematical — with their characteristics, strengths, limitations and suitable examples. State which method is appropriate for which type of research question.
3. Explain deduction and induction with reference to computer science research. Compare them in detail and explain how both are used together in the research process.
4. Discuss the theoretical approach to research in computing science. Explain the important formal models and the role of formal methods and verification.
5. Explain the algorithmic approach to computing research. Discuss algorithm design paradigms, methods of proving correctness, and complexity analysis.
6. Discuss software engineering research approaches. Explain the various empirical methods used and the measurement and validity issues involved.
7. What is mathematical modelling? Explain its steps, classification, common models used in computing, and its advantages and limitations.
8. Explain performance estimation and evaluation. Discuss performance metrics, the three evaluation techniques, and the common mistakes made in performance studies.
9. Compare analytical modelling, simulation and measurement as techniques of performance evaluation. Under what circumstances is each preferred?
10. Take any research claim in computer science and show how you would establish it using an appropriate combination of argument structure, proof method and performance evaluation.